def get_subtext(subtext, text):
    def get_next(subtext):
        a = i = p = 0
        m = len(subtext)
        next = [0] * m
        next[0] = m
        for i in range(1, m - 1):
            if (i >= p) or (i + next[i - a] >= p):
                if i >= p:
                    p = i
                    while (p < m) and (subtext[p] == subtext[p - i]):
                        p += 1
                    next[i] = p - i
                    a = i
                else:
                    next[i] = next[i - a] - 1
        return next

    a = i = p = 0
    m = len(subtext)
    next = get_next(subtext)
    n = len(text)
    extend = [0] * n
    result = []
    for i in range(1, n - 1):
        if (i >= p) or (i + next[i - a] >= p):  # i >= p 的作用：举个典型例子，text 和 subtext 无一字符相同
            if i >= p:
                p = i
            while (p < n) and (p - i < m) and (text[p] == subtext[p - i]):
                p += 1
            extend[i] = p - i
            if extend[i] == m:
                result.append(i)
            a = i
        else:
            extend[i] = next[i - a]
            if extend[i] == m:
                result.append(i)
    return result


'''
z函数
对于一个长度为 n 的字符串 s，定义函数 z[i] 表示 s 和 s[i,n-1]（即以 s[i] 开头的后缀）的最长公共前缀（LCP）的长度，则 z 被称为 s 的 Z 函数。特别地，z[0] = 0。
'''
def z_function(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r and z[i - l] < r - i + 1:
            z[i] = z[i - l]
        else:
            z[i] = max(0, r - i + 1)
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z




print(get_subtext("baaacbaaaaacaaaaacvc","baaacbaaaaacaaaaacvc"))
print(z_function("abca"))